      1  import java.util.NoSuchElementException;

      2

      3  /**

      4     An implementation of a doubly linked list.

      5  */

      6  public class LinkedList

      7  {

      8     private Node first;

      9     private Node last;

     10

     11     /**

     12        Constructs an empty linked list.

     13     */

     14     public LinkedList()

     15     {

     16        first = null;

     17        last = null;

     18     }

     19

     20     /**

     21        Returns the first element in the linked list.

     22        @return the first element in the linked list

     23     */

     24     public Object getFirst()

     25     {

     26        if (first == null) { throw new NoSuchElementException(); }

     27        return first.data;

     28     }

     29

     30     /**

     31        Removes the first element in the linked list.

     32        @return the removed element

     33     */

     34     public Object removeFirst()

     35     {

     36        if (first == null) { throw new NoSuchElementException(); }

     37        Object element = first.data;

     38        first = first.next;

     39        if (first == null) { last = null; } // List is now empty

     40        else { first.previous = null; }

     41        return element;

     42     }

     43

     44     /**

     45        Adds an element to the front of the linked list.

     46        @param element the element to add

     47     */

     48     public void addFirst(Object element)

     49     {

     50        Node newNode = new Node();

     51        newNode.data = element;

     52        newNode.next = first;

     53        newNode.previous = null;

     54        if (first == null) { last = newNode; }

     55        else { first.previous = newNode; }

     56        first = newNode;

     57     }

     58

     59     /**

     60        Returns the last element in the linked list.

     61        @return the last element in the linked list

     62     */

     63     public Object getLast()

     64     {

     65        if (last == null) { throw new NoSuchElementException(); }

     66        return last.data;

     67     }

     68

     69     /**

     70        Removes the last element in the linked list.

     71        @return the removed element

     72     */

     73     public Object removeLast()

     74     {

     75        if (last == null) { throw new NoSuchElementException(); }

     76        Object element = last.data;

     77        last = last.previous;

     78        if (last == null) { first = null; } // List is now empty

     79        else { last.next = null; }

     80        return element;

     81     }

     82

     83     /**

     84        Adds an element to the back of the linked list.

     85        @param element the element to add

     86     */

     87     public void addLast(Object element)

     88     {

     89        Node newNode = new Node();

     90        newNode.data = element;

     91        newNode.next = null;

     92        newNode.previous = last;

     93        if (last == null) { first = newNode; }

     94        else { last.next = newNode; }

     95        last = newNode;

     96     }

     97

     98     /**

     99        Returns an iterator for iterating through this list.

    100        @return an iterator for iterating through this list

    101     */

    102     public ListIterator listIterator()

    103     {

    104        return new LinkedListIterator();

    105     }

    106

    107     class Node

    108     {

    109        public Object data;

    110        public Node next;

    111        public Node previous;

    112     }

    113

    114     class LinkedListIterator implements ListIterator

    115     {

    116        private Node position;

    117        private boolean isAfterNext;

    118        private boolean isAfterPrevious;

    119

    120        /**

    121           Constructs an iterator that points to the front

    122           of the linked list.

    123        */

    124        public LinkedListIterator()

    125        {

    126           position = null;

    127           isAfterNext = false;

    128           isAfterPrevious = false;

    129        }

    130

    131        /**

    132           Moves the iterator past the next element.

    133           @return the traversed element

    134        */

    135        public Object next()

    136        {

    137           if (!hasNext()) { throw new NoSuchElementException(); }

    138           isAfterNext = true;

    139           isAfterPrevious = false;

    140

    141           if (position == null)

    142           {

    143              position = first;

    144           }

    145           else

    146           {

    147              position = position.next;

    148           }

    149

    150           return position.data;

    151        }

    152

    153        /**

    154           Tests if there is an element after the iterator position.

    155           @return true if there is an element after the iterator position

    156        */

    157        public boolean hasNext()

    158        {

    159           if (position == null)

    160           {

    161              return first != null;

    162           }

    163           else

    164           {

    165              return position.next != null;

    166           }

    167        }

    168

    169        /**

    170           Moves the iterator before the previous element.

    171           @return the traversed element

    172        */

    173        public Object previous()

    174        {

    175           if (!hasPrevious()) { throw new NoSuchElementException(); }

    176           isAfterNext = false;

    177           isAfterPrevious = true;

    178

    179           Object result = position.data;

    180           position = position.previous;

    181           return result;

    182        }

    183

    184        /**

    185           Tests if there is an element before the iterator position.

    186           @return true if there is an element before the iterator position

    187        */

    188        public boolean hasPrevious()

    189        {

    190           return position != null;

    191        }

    192

    193        /**

    194           Adds an element before the iterator position

    195           and moves the iterator past the inserted element.

    196           @param element the element to add

    197        */

    198        public void add(Object element)

    199        {

    200           if (position == null)

    201           {

    202              addFirst(element);

    203              position = first;

    204           }

    205           else if (position == last)

    206           {

    207              addLast(element);

    208              position = last;

    209           }

    210           else

    211           {

    212              Node newNode = new Node();

    213              newNode.data = element;

    214              newNode.next = position.next;

    215              newNode.next.previous = newNode;

    216              position.next = newNode;

    217              newNode.previous = position;

    218              position = newNode;

    219           }

    220

    221           isAfterNext = false;

    222           isAfterPrevious = false;

    223        }

    224

    225        /**

    226           Removes the last traversed element. This method may

    227           only be called after a call to the next() method.

    228        */

    229        public void remove()

    230        {

    231           Node positionToRemove = lastPosition();

    232

    233           if (positionToRemove == first)

    234           {

    235              removeFirst();

    236           }

    237           else if (positionToRemove == last)

    238           {

    239              removeLast();

    240           }

    241           else

    242           {

    243              positionToRemove.previous.next = positionToRemove.next;

    244              positionToRemove.next.previous = positionToRemove.previous;

    245           }

    246

    247           if (isAfterNext)

    248           {

    249              position = position.previous;

    250           }

    251

    252           isAfterNext = false;

    253           isAfterPrevious = false;

    254        }

    255

    256        /**

    257           Sets the last traversed element to a different value.

    258           @param element the element to set

    259        */

    260        public void set(Object element)

    261        {

    262           Node positionToSet = lastPosition();

    263           positionToSet.data = element;

    264        }

    265

    266        /**

    267           Returns the last node traversed by this iterator, or

    268           throws an IllegalStateException if there wasn't an immediately

    269           preceding call to next or previous.

    270           @return the last traversed node

    271        */

    272        private Node lastPosition()

    273        {

    274           if (isAfterNext)

    275           {

    276              return position;

    277           }

    278           else if (isAfterPrevious)

    279           {

    280              if (position == null)

    281              {

    282                 return first;

    283              }

    284              else

    285              {

    286                 return position.next;

    287              }

    288           }

    289           else { throw new IllegalStateException(); }

    290        }

    291     }

    292  }